// 把n个骰子扔在地上，所有骰子 朝上一面的点数之和为s，输入n,打印出s的所有可能的值出现的概率。需要一个浮点数返回答案，其中第i个元素代表这n个骰子这n个 中第i小的概率

// 暴力

var twoSun = function (n: number) {
  const map = new Map()
  const totalTimes = Math.pow(6, n)
  inner(0, 1)
  const res = []
  console.log(map)
  for (const times of map.values()) {
    res.push(times / totalTimes)
  }

  function inner(total: number, step: number) {

    if (step > n) {
      map.set(total, map.has(total) ? map.get(total) + 1 : 1)
      return
    }
    for (let i = 0; i <= 6; ++i) {
      inner(total + i, step + 1)
    }
  }

  return res
}
twoSun(3)

// 动态规划
// dp数组的含义 db[i][j] 代表i 枚骰子朝上的面到达j的总数
// 状态转移方程
// dp[i][j] = db[i-1][j-1] + db[i-1][j-2]+db[i-1][j-3]+db[i-1][j-4]+db[i-1][j-6]+db[i-1][j-6]

const twoSun2 = (n: number) => {
  const dp = new Array(n + 1)
  for (let i = 1; i < n; ++i) {
    dp[i] = new Array(67).fill(0)
  }
  for (let j = 1; j <= 6; ++j) {
    dp[1][j] = 1
  }
  for (let i = 2; i <= n; ++i) {
    for (let j = i; j <= 6 * i; ++j) {
      for (let k = 1; j - k > 0 && k <= 6; ++k) {
        dp[i][j] += dp[i - 1][j - k]
      }
    }
  }
  let totalTimes = Math.pow(6, n)
  const ans = []
  for (let j = n; j <= n * 6; ++j) {
    ans.push(dp[n][j] / totalTimes)
  }
  return ans
}